//给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。 
//
// 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。 
//
// 
//
// 示例 1： 
//
// 
//输入: s1 = "ab" s2 = "eidbaooo"
//输出: True
//解释: s2 包含 s1 的排列之一 ("ba").
// 
//
// 示例 2： 
//
// 
//输入: s1= "ab" s2 = "eidboaoo"
//输出: False
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s1.length, s2.length <= 10⁴ 
// s1 和 s2 仅包含小写字母 
// 
//
// 
//
// 
// 注意：本题与主站 567 题相同： https://leetcode-cn.com/problems/permutation-in-string/ 
//
// Related Topics 哈希表 双指针 字符串 滑动窗口 👍 110 👎 0


package LeetCode.editor.cn;


import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-01-16 11:44:37
 * @description LCR 014.字符串的排列
 
 */
 
public class MPnaiL {
    public static void main(String[] args) {
    //测试代码
    MPnaiL fun = new MPnaiL();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean checkInclusion(String p, String s) {
        int[] c = new int[128];
        //先初始化数组，把匹配串对应的字母标记次数
        for (char ch : p.toCharArray()) c[ch]++;
        int l = 0, r = 0;
        List<Integer> res = new ArrayList<>();
        while (r < s.length()) {
            //如果当前位置存在于匹配串种，消耗掉当前的位置，然后右边的位置往前
            if (c[s.charAt(r)] > 0) {
                c[s.charAt(r++)]--;
                //如果消耗到匹配的长度，就记录
                if (r - l == p.length()) res.add(l);
                //如果不匹配，说明右移左边界，复位计数器，直到条件再次满足
                //p种的资源相当于存粮，r没有见到存粮时，l会补给，补给后，r会立即消耗往前走
                //如果r遇见是存粮x中的子集x1中的一部分，后面r没有遇见存粮就不动了，l会立即补给x1个
                //即l只会比r快一步，最大可能慢x步

                // 找完一次异位词，其实就正好将count数组中的频次全部消耗为0
                // 此时右指针来到一个非p字符，或者虽然是p字符但count中已经没有频次可消耗了，于是赖着不走了
                // 左指针出动，开始为count数组作补给，
                // 对于非p字符，左指针补一口，右指针就吃一口，亦步亦趋，直到再次遇到p中字符，右指针才可能反超，
                // 注意，此时右指针消耗的频次，其实来自于左指针从前一个异位词那里补充的
            } else {
                //非匹配的串，消耗一个存一个，匹配的字符，消耗完一次会马上补充
                c[s.charAt(l++)]++;
            }
        }
        return !res.isEmpty();
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
